package com.insert;

/**
 * Created by HMF on 2021/07/08 11:17
 */

/**
 * 插入排序
 */
public class Solution {

    // 插入排序
    public static void insertSort(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }
        for (int i = 1; i < a.length; i++) {
            int temp = a[i]; // 把 a[i] 插入到 a[0 ~ i-1] 的有序子列表中， a[i]: 待插入数，需要暂存起来到 temp
            int j = i;
            if (a[j - 1] > temp) {
                // while 循环，移动有序列表，确定待插入数的位置
                while (j >= 1 && a[j - 1] > temp) {
                    a[j] = a[j - 1];
                    j--;
                }
            }
            a[j] = temp; // 插入待插入的数
        }
    }

    public static void main(String[] args) {
//        int[] array = {7, 3, 19, 40, 4, 7, 1};
        int[] array = {38, 65, 97, 76, 13, 27, 49};
        insertSort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}
